LeetCode 55 、跳跃游戏

一、题目描述

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 跳跃游戏（ LeetCode 55 ）:https://leetcode-cn.com/problems/jump-game/submissions/
class Solution {
    public boolean canJump(int[] nums) {

        // 设置数组，保存每个位置如果在当前位置出发，一次性可以到达的最远位置
        // 比如 nums 为 [ 2 , 4 , 5 , 3 , 1 , 0 , 6]
        // 那么对于 2 来说，可以跳到最远的位置是 5 那个位置，即索引为 2 的那个位置
        // 对于 4 来说，可以跳到最远的位置是 0 那个位置，即索引为 5 的那个位置
        // 对于 5 来说，可以跳到最远的位置超过了数组的范围
        int[] jump = new int[nums.length];

        // 初始化 jump
        for(int i = 0 ; i < nums.length ; i++){
            // jump[i] 就是当前的索引值 i 加上该位置可以跳跃的最大长度 nums[i]
            jump[i] = i + nums[i];
        }

        // 从数组下标为 0 的位置开始起跳，索引为 0
        int index = 0;

        // 设置变量 maxJump，用来记录可以到达的最远位置
        // 从数组下标为 0 的位置开始起跳，此时记录的最远距离为 jump[0]
        int maxJump = jump[0];

        // 开始起跳
        // 直到 index 到达数组尾部，index >= nums.length
        // 或者 index 超过 maxJump
        while(index < nums.length && index <= maxJump){
            
            // 如果发现可以跳到的最远距离 maxJump 小于 jump[index]
            if(maxJump < jump[index]){
                // 那么需要更新 maxJump
                maxJump = jump[index];
            }

            // index 向前移动
            index++;
        }

        // 循环结束后，如果 index 已经访问了 nums 中所有的元素
        if(index > nums.length - 1){
            // 说明可以到达最后一个下标
            return true;
        }

        // 否则说明无法到达最后一个下标
        return false;

    }
}

**2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 跳跃游戏（ LeetCode 55 ）:https://leetcode-cn.com/problems/jump-game/submissions/
class Solution {
public:
    bool canJump(vector<int>& nums) {
        // 设置数组，保存每个位置如果在当前位置出发，一次性可以到达的最远位置
        // 比如 nums 为 [ 2 , 4 , 5 , 3 , 1 , 0 , 6]
        // 那么对于 2 来说，可以跳到最远的位置是 5 那个位置，即索引为 2 的那个位置
        // 对于 4 来说，可以跳到最远的位置是 0 那个位置，即索引为 5 的那个位置
        // 对于 5 来说，可以跳到最远的位置超过了数组的范围
        vector<int> jump(nums.size());
        // 初始化 jump
        for(int i=0;i < nums.size(); i++){
            // jump[i] 就是当前的索引值 i 加上该位置可以跳跃的最大长度 nums[i]
            jump[i] = i + nums[i];
        }
        // 从数组下标为 0 的位置开始起跳，索引为 0
        int index = 0;
        // 设置变量 maxJump，用来记录可以到达的最远位置
        // 从数组下标为 0 的位置开始起跳，此时记录的最远距离为 jump[0]
        int maxJump = jump[0];
        // 开始起跳
        // 直到 index 到达数组尾部，index >= nums.length
        // 或者 index 超过 maxJump
        while(index<=maxJump && index < nums.size()){
            // 如果发现可以跳到的更远距离
            if(maxJump<jump[index]){
                maxJump = jump[index];  // 那么需要更新 maxJump
            }
            index++;   // index 向前移动
        }
        // 循环结束后，如果发现 index 的位置在数组 nums 的最后一个位置
        if(index > nums.size() - 1){
            return true;
        }
        return false;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 跳跃游戏（ LeetCode 55 ）:https://leetcode-cn.com/problems/jump-game/submissions/
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # 设置数组，保存每个位置如果在当前位置出发，一次性可以到达的最远位置
        # 比如 nums 为 [ 2 , 4 , 5 , 3 , 1 , 0 , 6]
        # 那么对于 2 来说，可以跳到最远的位置是 5 那个位置，即索引为 2 的那个位置
        # 对于 4 来说，可以跳到最远的位置是 0 那个位置，即索引为 5 的那个位置
        # 对于 5 来说，可以跳到最远的位置超过了数组的范围

        jump = list(range(len(nums)))

        # 初始化 jump
        for i in range(len(nums)) : 
            # jump[i] 就是当前的索引值 i 加上该位置可以跳跃的最大长度 nums[i]
            jump[i] = i + nums[i]
        

        # 从数组下标为 0 的位置开始起跳，索引为 0
        index = 0

        # 设置变量 maxJump，用来记录可以到达的最远位置
        # 从数组下标为 0 的位置开始起跳，此时记录的最远距离为 jump[0]
        maxJump = jump[0]

        # 开始起跳
        # 直到 index 到达数组尾部，index >= nums.length
        # 或者 index 超过 maxJump
        while index < len(nums) and index <= maxJump :
            
            # 如果发现可以跳到的最远距离 maxJump 小于 jump[index]
            if maxJump < jump[index] : 
                # 那么需要更新 maxJump
                maxJump = jump[index]
            

            # index 向前移动
            index += 1
        

        # 循环结束后，如果 index 已经访问了 nums 中所有的元素
        if index >len(nums) - 1 : 
            # 说明可以到达最后一个下标
            return True
        

        # 否则说明无法到达最后一个下标
        return False

四、复杂度分析

时间复杂度：O(n)，其中 n 为数组的大小。只需要访问 nums 数组一遍，共 n 个位置。

空间复杂度：O(1)，不需要额外的空间开销。